摘要：从理论上可知，Vernam密码的一次一密(One-Time-Pad)方案是不可破解的。但是，如果同一段密钥被用来加密多段密文，即多次一密(Many-Time-Pad)的情况下，加密方案就不再安全。本文以一次密码学课的作业为例，介绍Many-Time-Pad Attack的具体过程。

01. 问题背景

Vernam加密法也称一次一密(One-Time-Pad)，使用与明文等长的随机密钥，对原文进行加密。由于密文与原文没有任何统计关系，所以一次一密的方案理论上是不可破解的。但是为了达到这样的效果，最重要的条件是，一旦明文改变，就不能再使用本次的密文。否则，多次一密(Many-Time-Pad)的场景下，这种加密方式就不再安全。

02. 破解内容

现有6段使用Vernam加密过的字符串，但6段字符串总共使用了3个随机密钥，其中每个密钥都恰好使用了两次。6段明文分别是一段代码、一段莎士比亚的引言、一段歌词、三段其他的英语名言。需要破解出所有明文。

6段密文的下载地址：Github链接

03. 分析过程

本题的解决过程应该分为两步：

1. 判断六段密文中，哪些密文是公用的统一密钥；
2. 将配对后的密文进行破解。
   
   

密文配对

设两段明文为$p_1$和$p_2$，密钥为$c$，则加密后的密文分别为$p_1 \oplus c$和$p_2 \oplus c$。如果将两段密文再做一次异或，根据异或的性质，有$(p_1 \oplus c) \oplus (p_2 \oplus c) = p_1 \oplus p_2$，结果是两段明文直接异或的结果，与密钥无关。因此对于任意两段密文，如果它们共用了密钥，它们异或的结果就等价于它们对应的明文直接异或。

一段英文文本中，绝大部分字符应该都是小写字母，其次是空格和大写字母，还有少数标点符号。因此两段英文文本做异或，大多数位置上都是小写字母之间做异或。遍历任意小写字母之间异或的结果，我们发现，小写字母之间异或的结果取值范围为0x00-0x1F。因此，两段明文之间异或的结果分布应该集中在0x00-0x1F之间（其次是0x41-0x5A，即空格与小写字母之间异或）。

因此，我们可以将六段密文两两做异或，分析各位置上取值的分布，如果两段密文共用了密钥，取值应该主要分布在0x00-0x1F之间。而如果两段密文不共用密钥，取值的分布应该更为平均。密文之间异或结果在各区间的频数如下（按0x00-0x1F区间的频数降序）：

与我们的分析一致，密文1和3、2和5、4和6异或的分布集中在0x00-0x1F和0x40-0x5F之间，而其他配对异或结果的分布很平均。所以，我们可以断定，密文1和3、2和5、4和6分别共用了同一密钥。

密文破解

在确定了哪些密文共用的是同一密钥之后，下一步就是逐对破解。

破解时，我们最主要的依据是题干中的：“6段明文分别是一段代码、一段莎士比亚的引言、一段歌词、三段其他的英语名言。”这个条件大大缩小了语料库，同时也为我们提供了突破口。

为了方便验证猜想，我制作了一个前端工具（见第4部分）。页面的左右两边分别为一对密文，当在某个位置填入字符（猜想的明文）后，工具会自动在另一侧算出对应的明文。

由于空格与小写字母之间异或结果的取值范围为0x41-0x5A，我们可以通过这个范围去大致观察空格的分布。在密文2和5的结果中（如下），我们发现最后的18个位置几乎都是位于上述区间或者是0x00（空格与空格异或），不禁猜想，难道某个明文尾部是用空格填充的？

'05', '49', '1d', '11', '13', '0b', '52', '0d', 
'54', '21', '0e', '43', '11', '4f', '18', '59', 
'57', '11', '1b', '04', '49', '18', '1c', '0e', 
'4b', '40', '4f', '59', '69', '41', '4f', '1d', 
'09', '1a', '52', '04', '00', '4b', '45', '29', 
'1f', '54', '59', '1b', '1a', '00', '00', '00', 
'00', '1b', '00', '17', '00', '00', '1a', '07', 
'11', '00', '17', '00', '4e', '10', '0c', '18', 
'05', '50', '4e', '04', '48', '06', '0f', '00', 
'18', '00', '45', '43', '07', '48', '54', '2b', 
'09', '16', '53', '06', '13', '4e', '0d', '4c', 
'29', '04', '06', '4e', '43', '45', '0d', '36', 
'04', '0b', '16', '02', '11', '52', '65', '00', 
'00', '53', '0d', '0a', '1c', '1c', '00', '45', 
'41', '52', '00', '0d', '74', '48', '45', '00', 
'62', '45', '41', '54', '4c', '45', '53', '00'

于是将2和5其中一段明文的尾部18个字符设为空格，发现另一段明文的尾部为ear -The Beatles。原来是甲壳虫的歌词，我们的语料库范围进一步缩小。搜索甲壳虫含ear的歌词，找到了《Do You Want to Know a Secret》，其中含ear的句子为Let me whisper in your ear。由于我们不知道原文中具体大小写、标点的情况，所以我们从后往前填入，同时观察另一段明文的内容，为learn. -Albert Einstein，搜索可知，是爱因斯坦的名言”I never teach my pupils. I only attempt to provide the conditions in which they can learn.” 两段明文的出处都知道了，由于明文与网上查到的内容可能不完全一致，所以接下来交替着从后向前填入两段明文，注意处理标点、空格、大写的问题。结果如下：

密文2和5的明文是一段歌词和一段名言，它们在歌词和名言之后，都加上了作者的名字，然后用空格填补剩下的长度。这一点透露了文本的格式信息。由于剩下的4段文本中有一段是莎士比亚的名言，我们自然可以猜想，有一段明文的尾部应该是William Shakespeare，后面可能会有一些空格。在1和3、4和6都进行试验，发现如果将1和3的一段明文的尾部设为William Shakespeare，另一段明文的尾部为k rules Neil Gaiman，是尼尔·盖曼的名言，语料库范围成功缩小，搜索可知，是”Now go and make interesting mistakes, make amazing mistakes, make glorious and fantastic mistakes. Break rules.” 从后往前依次填入，发现莎士比亚的引言是出自《无事生非》的”Therefore all hearts in love use their own tongues. Let every eye negotiate for itself. And trust no agent” 两段明文的出处都知道了，跟上面一样，由于明文与原文不完全一致，交替着从后向前填入两段明文，结果如下：

最后剩下的1和3对应的是一段代码和一段名言。破解这一对的突破口是代码。因为另一段文本是名言，其中的字符应该只可能是大小写字母、空格、常见标点，因此我们可以猜测代码所用的语言（C/C++、Java、Python等），然后用该语言的关键字（对于C/C++，如int、char、double、if、for、printf等）在原文中每个位置进行匹配，看另一段明文中解析出的字符是否合法，以此判断该位置是不是能放该关键字。然后在根据另一段解析出的文本，利用互联网提供的语料库进行搜索。

在试验时，首先尝试最长的关键词printf，因为它能够提供最多的信息。我发现在25-31的位置上可以填入printf(，另一段解析出的是yoursel，在111-117的位置上也可以填入printf(，另一段解析出的是eg. -S，看来就是名言的末尾了，猜测110位置是空格，则另一段是l，于是名言最后一个词很可能是leg（或者leg是一个后缀）。然后我们最希望获得的是完整的人名，这样我们基本就能够确定这一段名言了。继续猜测printf(下面的内容，很可能应该是printf("____");这样的格式，于是我们尝试不同的打印长度，发现如果打印长度是4时，右侧都是合法字符，人名是St____tru。暂时联想不出合适的人名。

接着尝试别的关键词，在另一段中会出现一些英文单词的片段，辅助以英文词库，来猜测完整的单词，然后反过来对代码进行补全。交替使用这种方式不断尝试，其中成功试验的结果如下：

• 我们发现在1-4上可以填入int，另一段解析出的是mak，由于0的位置上只剩一个字符，根据代码的特点，猜测是{，于是另一段变为C mak（猜想应该是C makes）。
• 由于开头有一个左大括号，刚刚我们在结尾还有两个空位置，如果126上填入}，那么人名就变为了St____trup，看起来是合理的。
• 12-16上可以填入char，另一段为asy t（猜想应该是easy to）。

现在名言中我们已经获得的片段是C mak(C makes)、asy t(easy to)、leg.，然后人名是St____trup。利用搜索引擎稍加搜索，可以找到它是“C++之父”Stroustrup的名言”C makes it easy to shoot yourself in the foot; C++ makes it harder, but when you do it blows your whole leg off.” 将这一段文本逐步填入，注意处理符号、空格，保证代码也是合理的。于是我们可以得到如下结果：

04.代码

前端工具地址：Github链接。

工具是一个静态页面。使用时将URL中的querystring设置为“?left=i&right=j”，即可在左侧显示密文i，右侧显示密文j，如your_url?left=2&right=5会显示密文2和密文5。如果querystring为空，默认显示密文1和密文3。